<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Legendre-Symbol</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Legendre-Symbol"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Legendre-Symbol rootpage-Legendre-Symbol skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Legendre-Symbol</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Das <b>Legendre-Symbol</b> ist eine Kurzschreibweise, die in der <a href="Zahlentheorie" title="Zahlentheorie">Zahlentheorie</a>, einem <a href="Teilgebiet_der_Mathematik" class="mw-redirect" title="Teilgebiet der Mathematik">Teilgebiet der Mathematik</a>, verwendet wird. Es ist nach dem französischen Mathematiker <a href="Adrien-Marie_Legendre" title="Adrien-Marie Legendre">Adrien-Marie Legendre</a> benannt.
</p>
<div class="mw-heading mw-heading2"><h2 id="Definition_und_Notation">Definition und Notation</h2></div>
<p>Das Legendre-Symbol gibt an, ob die Zahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> <a href="Quadratischer_Rest" title="Quadratischer Rest">quadratischer Rest modulo <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span></a> oder quadratischer Nichtrest modulo <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> ist. Dabei ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> eine ganze Zahl und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> eine ungerade <a href="Primzahl" title="Primzahl">Primzahl</a>.
</p><p>Es gilt
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1,&{\text{wenn }}a{\text{ quadratischer Rest modulo }}p{\text{ und kein Vielfaches von }}p{\text{ ist}},\\-1,&{\text{wenn }}a{\text{ quadratischer Nichtrest modulo }}p{\text{ ist}},\\0,&{\text{wenn }}a{\text{ ein Vielfaches von }}p{\text{ ist}}.\end{cases}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>a</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>{</mo>
<mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false">
<mtr>
<mtd>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mtext>wenn </mtext>
</mrow>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> quadratischer Rest modulo </mtext>
</mrow>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> und kein Vielfaches von </mtext>
</mrow>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> ist</mtext>
</mrow>
<mo>,</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mtext>wenn </mtext>
</mrow>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> quadratischer Nichtrest modulo </mtext>
</mrow>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> ist</mtext>
</mrow>
<mo>,</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mtext>wenn </mtext>
</mrow>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> ein Vielfaches von </mtext>
</mrow>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext> ist</mtext>
</mrow>
<mo>.</mo>
</mtd>
</mtr>
</mtable>
<mo fence="true" stretchy="true" symmetric="true"></mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1,&{\text{wenn }}a{\text{ quadratischer Rest modulo }}p{\text{ und kein Vielfaches von }}p{\text{ ist}},\\-1,&{\text{wenn }}a{\text{ quadratischer Nichtrest modulo }}p{\text{ ist}},\\0,&{\text{wenn }}a{\text{ ein Vielfaches von }}p{\text{ ist}}.\end{cases}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ef05e4d21e511031184e1e4bf413d0fc868b7cb2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:83.528ex; height:8.509ex;" alt="{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1,&{\text{wenn }}a{\text{ quadratischer Rest modulo }}p{\text{ und kein Vielfaches von }}p{\text{ ist}},\\-1,&{\text{wenn }}a{\text{ quadratischer Nichtrest modulo }}p{\text{ ist}},\\0,&{\text{wenn }}a{\text{ ein Vielfaches von }}p{\text{ ist}}.\end{cases}}}" loading="lazy"></span></dd></dl>
<p>Das Legendre-Symbol ist ein Spezialisierung des <a href="Jacobi-Symbol" title="Jacobi-Symbol">Jacobi-Symbols</a>, das wiederum eine Spezialisierung des <a href="Kronecker-Symbol" title="Kronecker-Symbol">Kronecker-Symbols</a> ist. Alle drei Symbole benutzen daher unmissverständlich dieselbe Schreibweise. Weitere Notationsvarianten für das Legendre-Symbol sind <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a/p)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mi>p</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (a/p)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/04651861aec7cb90f4d4e863b846e3cb5f5d0dfc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.371ex; height:2.843ex;" alt="{\displaystyle (a/p)}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(a,p)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>L</mi>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>,</mo>
<mi>p</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle L(a,p)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c07813499283d234a6b7ede8ecacba160e3cbdf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.825ex; height:2.843ex;" alt="{\displaystyle L(a,p)}" loading="lazy"></span>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Berechnung">Berechnung</h2></div>
<p>Das <b>eulersche Kriterium</b> gibt eine mögliche Berechnungsmethode zum Legendre-Symbol an:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>a</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>≡<!-- ≡ --></mo>
<msup>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>p</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</msup>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="1em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mi>p</mi>
<mo stretchy="false">)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ad22849f219e1b4aed9b2c4ebd71928119cf2fb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.114ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}}" loading="lazy"></span>.</dd></dl>
<p>Eine weitere Berechnungsmöglichkeit liefert das <a href="Lemma_von_Zolotareff" title="Lemma von Zolotareff">Lemma von Zolotareff</a> mit
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{p}}\right)=\operatorname {sgn} (\pi _{a,p}),}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>a</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mi>sgn</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>π<!-- π --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>a</mi>
<mo>,</mo>
<mi>p</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)=\operatorname {sgn} (\pi _{a,p}),}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a7b75b63ccf9a2579e666c6ab375fb662c3d2e04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:18.124ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{p}}\right)=\operatorname {sgn} (\pi _{a,p}),}" loading="lazy"></span></dd></dl>
<p>wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{a,p}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>π<!-- π --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>a</mi>
<mo>,</mo>
<mi>p</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \pi _{a,p}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b0d89c086376d7edeffb122e92cb28ae2978fd47.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.711ex; height:2.343ex;" alt="{\displaystyle \pi _{a,p}}" loading="lazy"></span>, die durch
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>π<!-- π --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>a</mi>
<mo>,</mo>
<mi>p</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
<mo>≡<!-- ≡ --></mo>
<mi>a</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>k</mi>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="1em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mi>p</mi>
<mo stretchy="false">)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e9805d78ff8d8b4f948ecd7bcd52532d5599f62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.804ex; height:3.009ex;" alt="{\displaystyle \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}}}" loading="lazy"></span></dd></dl>
<p>definierte <a href="Permutation" title="Permutation">Permutation</a> der Zahlen von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=0,\dotsc p-1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>=</mo>
<mn>0</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mi>p</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k=0,\dotsc p-1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfa6cf7ab35fd57e60729d02bbaa5cb2cf144f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.789ex; height:2.509ex;" alt="{\displaystyle k=0,\dotsc p-1}" loading="lazy"></span> ist, und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {sgn} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>sgn</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {sgn} }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec838dfd8a4a659b2877f93a6b53f22fc7777d07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.371ex; height:2.009ex;" alt="{\displaystyle \operatorname {sgn} }" loading="lazy"></span> das <a href="Vorzeichen_(Permutation)" title="Vorzeichen (Permutation)">Vorzeichen</a> einer Permutation bezeichnet.
</p>
<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>
<p>2 ist quadratischer Rest modulo 7 – in der Tat ist ja <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\equiv 3^{2}{\pmod {7}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo>≡<!-- ≡ --></mo>
<msup>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="1em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mn>7</mn>
<mo stretchy="false">)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2\equiv 3^{2}{\pmod {7}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe0d1f519c48b58fcaefa5e19f583dce50e08ee3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.324ex; height:3.176ex;" alt="{\displaystyle 2\equiv 3^{2}{\pmod {7}}}" loading="lazy"></span>:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {2}{7}}\right)\equiv 2^{\frac {7-1}{2}}=2^{3}\equiv 1\mod 7}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>2</mn>
<mn>7</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>≡<!-- ≡ --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>7</mn>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</msup>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>≡<!-- ≡ --></mo>
<mn>1</mn>
<mspace width="1em"></mspace>
<mi>mod</mi>
<mspace width="thinmathspace"></mspace>
<mspace width="thinmathspace"></mspace>
<mn>7</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {2}{7}}\right)\equiv 2^{\frac {7-1}{2}}=2^{3}\equiv 1\mod 7}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3d6ed8ea8479994357cd3e5278f7ac6b8775fd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:32.122ex; height:6.176ex;" alt="{\displaystyle \left({\frac {2}{7}}\right)\equiv 2^{\frac {7-1}{2}}=2^{3}\equiv 1\mod 7}" loading="lazy"></span></dd></dl>
<p>5 ist quadratischer Nichtrest modulo 7:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {5}{7}}\right)\equiv 5^{\frac {7-1}{2}}=5^{3}\equiv 6\equiv -1\mod 7}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>5</mn>
<mn>7</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>≡<!-- ≡ --></mo>
<msup>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>7</mn>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</msup>
<mo>=</mo>
<msup>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>≡<!-- ≡ --></mo>
<mn>6</mn>
<mo>≡<!-- ≡ --></mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mspace width="1em"></mspace>
<mi>mod</mi>
<mspace width="thinmathspace"></mspace>
<mspace width="thinmathspace"></mspace>
<mn>7</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {5}{7}}\right)\equiv 5^{\frac {7-1}{2}}=5^{3}\equiv 6\equiv -1\mod 7}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f61ae15f410f98d94f91582b380c33806e83532b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:38.191ex; height:6.176ex;" alt="{\displaystyle \left({\frac {5}{7}}\right)\equiv 5^{\frac {7-1}{2}}=5^{3}\equiv 6\equiv -1\mod 7}" loading="lazy"></span></dd></dl>
<p>14 ist durch 7 teilbar (also weder Rest noch Nichtrest von 7):
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {14}{7}}\right)\equiv 14^{\frac {7-1}{2}}=14^{3}\equiv 0\mod 7}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>14</mn>
<mn>7</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>≡<!-- ≡ --></mo>
<msup>
<mn>14</mn>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>7</mn>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</msup>
<mo>=</mo>
<msup>
<mn>14</mn>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>≡<!-- ≡ --></mo>
<mn>0</mn>
<mspace width="1em"></mspace>
<mi>mod</mi>
<mspace width="thinmathspace"></mspace>
<mspace width="thinmathspace"></mspace>
<mn>7</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {14}{7}}\right)\equiv 14^{\frac {7-1}{2}}=14^{3}\equiv 0\mod 7}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac36bd4f0e1ad9a349d894a8c34d7c0b60df5a90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:35.609ex; height:6.176ex;" alt="{\displaystyle \left({\frac {14}{7}}\right)\equiv 14^{\frac {7-1}{2}}=14^{3}\equiv 0\mod 7}" loading="lazy"></span></dd></dl>
<div class="mw-heading mw-heading2"><h2 id="Rechenregeln">Rechenregeln</h2></div>
<p>Das <a href="Quadratisches_Reziprozit%C3%A4tsgesetz" title="Quadratisches Reziprozitätsgesetz">quadratische Reziprozitätsgesetz</a> macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.
</p><p>Außerdem gelten für alle ganze Zahlen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle b}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> und alle Primzahlen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> folgende Rechenregeln:
</p>
<ul><li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\equiv b{\pmod {p}}\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
<mo>≡<!-- ≡ --></mo>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="1em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mi>p</mi>
<mo stretchy="false">)</mo>
</mrow>
<mo stretchy="false">⇒<!-- ⇒ --></mo>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>a</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>b</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a\equiv b{\pmod {p}}\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f98cdc8e6f0011d0f648d19c9c68b9c24d7ea695.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:33.806ex; height:6.176ex;" alt="{\displaystyle a\equiv b{\pmod {p}}\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}" loading="lazy"></span></li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)=\left({\frac {a\cdot b}{p}}\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>a</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>⋅<!-- ⋅ --></mo>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>b</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>a</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>b</mi>
</mrow>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)=\left({\frac {a\cdot b}{p}}\right)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7460396f7d915f34ddd23e85e81a185140a1e09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:23.855ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)=\left({\frac {a\cdot b}{p}}\right)}" loading="lazy"></span></li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{k=1}^{p-1}\left({\frac {k}{p}}\right)=0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>p</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</munderover>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>k</mi>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \sum _{k=1}^{p-1}\left({\frac {k}{p}}\right)=0}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75de1fbe7594b29847ed1a2d1a54403214747702.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:13.472ex; height:7.343ex;" alt="{\displaystyle \sum _{k=1}^{p-1}\left({\frac {k}{p}}\right)=0}" loading="lazy"></span>.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Spezielle_Werte">Spezielle Werte</h2></div>
<p>Es gilt
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {1}{p}}\right)=1,}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {1}{p}}\right)=1,}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ed7952a55956def1e1b9a064837ded3ce494c887.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:10.334ex; height:6.176ex;" alt="{\displaystyle \left({\frac {1}{p}}\right)=1,}" loading="lazy"></span></dd>
<dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\mbox{ oder }}7{\pmod {8}},\\-1,&{\mbox{ für }}p\equiv 3{\mbox{ oder }}5{\pmod {8}},\end{cases}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>2</mn>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<msup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>8</mn>
</mfrac>
</mrow>
</msup>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>{</mo>
<mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false">
<mtr>
<mtd>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> für </mtext>
</mstyle>
</mrow>
<mi>p</mi>
<mo>≡<!-- ≡ --></mo>
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> oder </mtext>
</mstyle>
</mrow>
<mn>7</mn>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="0.444em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mn>8</mn>
<mo stretchy="false">)</mo>
</mrow>
<mo>,</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> für </mtext>
</mstyle>
</mrow>
<mi>p</mi>
<mo>≡<!-- ≡ --></mo>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> oder </mtext>
</mstyle>
</mrow>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="0.444em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mn>8</mn>
<mo stretchy="false">)</mo>
</mrow>
<mo>,</mo>
</mtd>
</mtr>
</mtable>
<mo fence="true" stretchy="true" symmetric="true"></mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\mbox{ oder }}7{\pmod {8}},\\-1,&{\mbox{ für }}p\equiv 3{\mbox{ oder }}5{\pmod {8}},\end{cases}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba46c2bd97b30b158077743e5dc2fa2cccc9a7e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:55.771ex; height:7.509ex;" alt="{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\mbox{ oder }}7{\pmod {8}},\\-1,&{\mbox{ für }}p\equiv 3{\mbox{ oder }}5{\pmod {8}},\end{cases}}}" loading="lazy"></span></dd>
<dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\pmod {4}},\\-1,&{\mbox{ für }}p\equiv 3{\pmod {4}}.\end{cases}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>p</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</msup>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>{</mo>
<mtable columnalign="left left" rowspacing=".2em" columnspacing="1em" displaystyle="false">
<mtr>
<mtd>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> für </mtext>
</mstyle>
</mrow>
<mi>p</mi>
<mo>≡<!-- ≡ --></mo>
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="0.444em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mn>4</mn>
<mo stretchy="false">)</mo>
</mrow>
<mo>,</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
</mtd>
<mtd>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext> für </mtext>
</mstyle>
</mrow>
<mi>p</mi>
<mo>≡<!-- ≡ --></mo>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<mspace width="0.444em"></mspace>
<mo stretchy="false">(</mo>
<mi>mod</mi>
<mspace width="0.333em"></mspace>
<mn>4</mn>
<mo stretchy="false">)</mo>
</mrow>
<mo>.</mo>
</mtd>
</mtr>
</mtable>
<mo fence="true" stretchy="true" symmetric="true"></mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\pmod {4}},\\-1,&{\mbox{ für }}p\equiv 3{\pmod {4}}.\end{cases}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a6d85a9c12857462ba3a7c7234a16a4059beef0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:50.049ex; height:7.509ex;" alt="{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\pmod {4}},\\-1,&{\mbox{ für }}p\equiv 3{\pmod {4}}.\end{cases}}}" loading="lazy"></span></dd></dl>
<p>Diese speziellen Werte reichen aus, um jedes nicht-verschwindende Legendre-Symbol durch wiederholtes Aufteilen des „Zählers“ in Primfaktoren, Anwenden des <a href="Quadratisches_Reziprozit%C3%A4tsgesetz" title="Quadratisches Reziprozitätsgesetz">quadratischen Reziprozitätsgesetzes</a> und modulo-Reduktion zu berechnen. So ist zum Beispiel
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {10}{31}}\right)=\left({\frac {2}{31}}\right)\left({\frac {5}{31}}\right)=1\cdot (-1)^{{\frac {5-1}{2}}{\frac {31-1}{2}}}\left({\frac {31}{5}}\right)=\left({\frac {1}{5}}\right)=1.}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>10</mn>
<mn>31</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>2</mn>
<mn>31</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>5</mn>
<mn>31</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mn>1</mn>
<mo>⋅<!-- ⋅ --></mo>
<mo stretchy="false">(</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>5</mn>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>31</mn>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</mrow>
</msup>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>31</mn>
<mn>5</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mn>5</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mn>1.</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {10}{31}}\right)=\left({\frac {2}{31}}\right)\left({\frac {5}{31}}\right)=1\cdot (-1)^{{\frac {5-1}{2}}{\frac {31-1}{2}}}\left({\frac {31}{5}}\right)=\left({\frac {1}{5}}\right)=1.}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/13d7aea372c45b82c02ed997a1887e0761870aa2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:61.665ex; height:6.176ex;" alt="{\displaystyle \left({\frac {10}{31}}\right)=\left({\frac {2}{31}}\right)\left({\frac {5}{31}}\right)=1\cdot (-1)^{{\frac {5-1}{2}}{\frac {31-1}{2}}}\left({\frac {31}{5}}\right)=\left({\frac {1}{5}}\right)=1.}" loading="lazy"></span></dd></dl>
<div class="mw-heading mw-heading2"><h2 id="Die_besondere_Stellung_der_Zahl_3">Die besondere Stellung der Zahl 3</h2></div>
<p>Die Zahl 3 liefert bei der Ganzzahldivision als Modulo die Werte 0, 1 und −1 zurück. Dies entspricht genau den Werten des Legendre-Symbols. Es gilt also:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{3}}\right)\equiv a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>a</mi>
<mn>3</mn>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>≡<!-- ≡ --></mo>
<msup>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>3</mn>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</msup>
<mtext> </mtext>
<mi>mod</mi>
<mo><!-- --></mo>
<mtext> </mtext>
<mn>3</mn>
<mo>=</mo>
<mi>a</mi>
<mtext> </mtext>
<mi>mod</mi>
<mo><!-- --></mo>
<mtext> </mtext>
<mn>3</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{3}}\right)\equiv a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91f2ef424e5f518d0ae5f55e9a697308c35d0716.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:31.917ex; height:5.176ex;" alt="{\displaystyle \left({\frac {a}{3}}\right)\equiv a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3}" loading="lazy"></span></dd></dl>
<p>Andererseits gilt auch:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {3}{p}}\right)=\prod _{l=1}^{\frac {p-1}{2}}\left[3-4\,\sin ^{2}{\left({\frac {2\pi l}{p}}\right)}\right]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>3</mn>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
<mo>=</mo>
<munderover>
<mo>∏<!-- ∏ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>l</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>p</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
</munderover>
<mrow>
<mo>[</mo>
<mrow>
<mn>3</mn>
<mo>−<!-- − --></mo>
<mn>4</mn>
<mspace width="thinmathspace"></mspace>
<msup>
<mi>sin</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo><!-- --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mn>2</mn>
<mi>π<!-- π --></mi>
<mi>l</mi>
</mrow>
<mi>p</mi>
</mfrac>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
</mrow>
<mo>]</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \left({\frac {3}{p}}\right)=\prod _{l=1}^{\frac {p-1}{2}}\left[3-4\,\sin ^{2}{\left({\frac {2\pi l}{p}}\right)}\right]}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/866dc759fb9e95ee13ec36bdc5413bfc6dde4a70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:32.262ex; height:8.843ex;" alt="{\displaystyle \left({\frac {3}{p}}\right)=\prod _{l=1}^{\frac {p-1}{2}}\left[3-4\,\sin ^{2}{\left({\frac {2\pi l}{p}}\right)}\right]}" loading="lazy"></span></dd></dl>
<div class="mw-heading mw-heading2"><h2 id="Besonderheiten_bei_Primzahlen">Besonderheiten bei Primzahlen</h2></div>
<p>Siehe dazu unter <a href="Pythagoreische_Primzahl" title="Pythagoreische Primzahl">Pythagoreische Primzahl</a>.
</p></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-04-19" href="https://de.wikipedia.org/wiki/?title=Legendre-Symbol&oldid=255286446">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>